package algorithm;



import java.math.BigInteger;
import java.util.List;
import java.util.ArrayList;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: NiceFun
 * @description: 好方法
 * @date 2021/4/714:19
 * @since V1.0
 */
public class NiceFun {

    //求质数
    public void 质数1(){
        int n=1000;
        int j;
        int res = 0;
        boolean sgin;
        for (int i = 2; i <= n; i++) {
            if(i % 2 == 0 && i != 2  )  continue; //偶数和1排除

            sgin= true;
            for (j = 2; j <= Math.sqrt(i) ; j++) {
                if (i % j == 0) {
                    sgin = false;
                    break;
                }
            }

            //打印
            if (sgin) {
                res = i;
                System.out.println(i);
            }
        }
        System.out.println("结果"+res);
    }

    //求质数
    public void 质数2(int n){
        long start = System.currentTimeMillis();    //取开始时间
        //素数总和
        int sum = 0;
        //1000万以内的所有素数
        //用数组将1000万以内的数分为两大派系，素数用0代替数值，合数用1代替数值；
        //一开始默认全部为素数，所以值全部为0，等到开始筛选的时候再把为合数的赋值为1
        int num[] = new int[n];
        num[0] = 1;          //由于1规定不是素数，所以要提前用1标值
        //根据埃氏筛法的结论，要得到自然数  N 以内的全部素数，必须把不大于" 二次根号  N "的所有素数的倍数剔除，剩下的就是素数
        double prescription = Math.sqrt(n);
        for (int i = 2; i <= prescription; i++) {
            //开始把所有素数的倍数剔除，剩下的就是素数
            for (int j = i*i; j <= n; j+=i) {
                //从i*i开始去除，因为比i*i小的倍数，已经在前面去除过了
                //例如：i=5
                //5的2倍（10），3倍（15），在i=2的时候，已经去除过了

                num[j-1] = 1;   //把素数的倍数剔除，也就是赋值为1，不是素数就是合数
            }
        }
        //遍历数组，把值为0的数全部统计出来，得到素数之和
        for (int i = 0; i < num.length; i++) {
            if(num[i]==0)
                sum++;
        }
        System.out.println(n+"以内的素数有"+sum+"个");
        long end = System.currentTimeMillis();
        System.out.println("The time cost is " + (end - start));
    }

    static List<String> list =  new ArrayList<>();

    public static void main(String[] args) {
        System.out.println(myPow(3,5));
    }
    //快速幂
    public static double myPow(double x, int n) {
        if(x == 0) return 0;
        long b = n;
        double res = 1.0;
        if(b < 0) {
            x = 1 / x;
            b = -b;
        }
        while(b > 0) {
            if((b & 1) == 1) res *= x;
            x *= x;
            b >>= 1;
        }
        return res;
    }

    //求最大公约数
    public static  void 公约数(){
        BigInteger result=new BigInteger(String.valueOf(list.get(0)));
        for(int i=1;i<list.size();i++){
            result=result.gcd(new BigInteger(String.valueOf(list.get(i))));
        }
        System.out.println(result.intValue());
    }


    //所有子序列
    public List<List<Integer>> 枚举(int[] nums) {
        List<Integer> t = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<>();
        //假如n为3
        int n = nums.length;
        //mask < 1000
        for (int mask = 0; mask < (1 << n); ++mask) {
            t.clear();
            for (int i = 0; i < n; ++i) {
                //假设mask为011时
                //011 & 001 ; 011 & 010 ; 011 & 100
                //add(nums[0])  add(nums[1]) ===>  [1,2]
                if ((mask & (1 << i)) != 0) {
                    t.add(nums[i]);
                }
            }
            ans.add(new ArrayList<Integer>(t));
        }
        return ans;
    }




}
